import java.util.List;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-23
 * Time: 10:21
 */
public class Solution3 {
    public ListNode reverse(ListNode head){
        ListNode pre=null;
        while (head!=null){
            ListNode curNext=head.next;
            head.next=pre;
            pre=head;
            head=curNext;
        }
        return pre;
    }
    public boolean isPail (ListNode head) {
        //方法三：双指针找到中点，反转后半部分链表，然后依次比较两个链表的各个值(推荐使用，最优解)
        /*时间复杂度是O(n),n是链表的长度，双指针找打中间节点遍历半个链表，后序反转链表为O(n),然后再遍历两份半个链表
        * 空间复杂度是O(1),没有使用额外的空间*/
        if(head==null){
            //空链表默认是回文链表
            return true;
        }
        //快慢指针找中间节点模板
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //此时slow的位置就是中间节点,也作为后半部分要翻转链表的头结点
        slow=reverse(slow);
        fast=head; //fast回到头结点，作为前半部分的头结点
        //比较两个部分的各个值，直到slow到了链表尾部
        while (slow!=null){
            if(fast.val!= slow.val){
                return false;
            }
            fast=fast.next;
            slow=slow.next;
        }
        return true;
    }
}
